package 字符串重排;

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * @param str string字符串
     * @return string字符串
     */
    public String rearrangestring(String str) {
        // write code here
        int n = str.length(), len = 0;
        int[] cnt = new int[26];
        PII[] p = new PII[26];
        for (int i = 0; i < n; i++) {
            cnt[str.charAt(i) - 'a']++;
        }
        for (int i = 0; i < 26; i++) {
            if (cnt[i] > 0) {
                p[len++] = new PII((char) (i + 'a'), cnt[i]);
            }
        }
        Arrays.sort(p, 0, len);
        int m = (n + 1) / 2;
        if (p[0].cnt > m) {
            return "";
        }
        char[] ret = new char[n];
        int t = m, i = 0, k = 0,j=1;
        while (t-- > 0) {
            ret[i] = p[k].x;
            i += 2;
            p[k].cnt--;
            if (p[k].cnt <= 0) {
                k++;
            }
        }
        t = n - m;
        while (t-->0){
            ret[j]=p[k].x;
            j+=2;
            p[k].cnt--;
            if (p[k].cnt <= 0) {
                k++;
            }
        }
        StringBuilder s = new StringBuilder();
        for (int l = 0; l < n; l++) {
            s.append(ret[l]);
        }
        return s.toString();
    }
}

class PII implements Comparable<PII> {
    char x;
    int cnt;

    public PII(char x, int cnt) {
        this.x = x;
        this.cnt = cnt;
    }

    @Override
    public int compareTo(PII o) {
        return Integer.compare(o.cnt, this.cnt);
    }
}